package com.heima.leetcode.datastructure.stack;


import java.util.LinkedList;
import java.util.List;
// 后缀表达式又叫逆波兰表达法：RPN
// 从左向右进行计算
// 不必考虑运算符优先级，即不用包含括号

/**
 * <h3>中缀表达式转成后缀表达式，以及后缀表达式求值 150</h3>
 */
public class InfixToPRN {
    // 一、计算后缀表达式
    // 遍历传进来的String[]数组（假定数组元素都合法且匹配），
    // 遇到数字就压入栈中，
    // 遇到运算符就弹出栈顶的两个元素和运算符参与运算，运算结果压入栈中，
    // 直到遍历结束，弹出栈顶元素也是栈中最后一个元素

    // 二、中缀表达式转后缀表达式
    // 遍历中缀表达式的字符串，
    // 1、如果遇到字符或者说非运算符并且非括号，则直接到后缀表达式的字符串中，
    // 2、如果遇到运算符，
    //    （1）如果栈为空或者栈顶为左括号，则直接压入栈顶，
    //    （2）如果栈非空且栈顶不为左括号，则与栈顶元素的运算符进行优先级比较，
    //         [1]如果栈顶运算符的优先级低，则将遇到的运算符压入栈顶，
    //         [2]如果栈顶运算符的优先级高或等，则弹出栈顶运算符并加到后缀表达式的字符串中，
    //    （3）再重复（1）（2）
    // 3、如果遇到的是左括号，则直接压入栈顶，
    // 4、如果遇到的是右括号，则一直弹出栈顶运算符，直到弹出第一个左括号截止，把弹出的运算符加到后缀表达式中去
    // 5、如果中缀表达式遍历结束，则将栈中的运算符依次弹出，加到后缀表达式中
    // |  |
    // |  |
    // |  |
    // |  |
    // |  |
    // |  |
    // |  |
    // a+b => ab+
    // a+b-c => ab+c-
    // a*b+c => ab*c+
    // a+b*c => abc*+
    // a+b*c-d => abc*+d-
    // (a+b)*c => ab+c*
    // (a*b+c-d)*e => ab*c+d-e*
    // f-(a-b*c/d)*e => fabc*d/-e*-
    // f-(a-b*c/d)*e => fabc*d/-e*-
    // a-(b-c+(d-e*f))+g => abc-def*-+-g+

    /**
     * 计算后缀表达式
     *
     * @param tokens 记录后缀表达式的字符串数组，用字符串是因为58这种多位数
     * @return 计算结果
     */
    public static int evalRPN(String[] tokens) {
        LinkedList<Integer> stack = new LinkedList<>();
        for (String token : tokens) {
            switch (token) {
                case "+" -> {
                    Integer num2 = stack.pop();
                    Integer num1 = stack.pop();
                    stack.push(num1 + num2);
                }
                case "-" -> {
                    Integer num2 = stack.pop();
                    Integer num1 = stack.pop();
                    stack.push(num1 - num2);
                }
                case "*" -> {
                    Integer num2 = stack.pop();
                    Integer num1 = stack.pop();
                    stack.push(num1 * num2);
                }
                case "/" -> {
                    Integer num2 = stack.pop();
                    Integer num1 = stack.pop();
                    stack.push(num1 / num2);
                }
                case "" -> {
                }
                default -> stack.push(Integer.parseInt(token));
            }
        }
        return stack.pop();
    }

    /**
     * 中缀表达式转后缀表达式
     *
     * @param exp 中缀表达式
     * @return 后缀表达式
     */
    public static String infixToSuffix(String exp) {
        StringBuilder builder = new StringBuilder(exp.length()); // 用于构造后缀表达式
        LinkedList<Character> stack = new LinkedList<>();
        // 遍历中缀表达式
        for (int i = 0; i < exp.length(); i++) {
            char c = exp.charAt(i);
            switch (c) {
                // 处理左括号
                case '(' -> // 直接压入栈中
                        stack.push(c);
                // 处理右括号
                case ')' -> {
                    // 弹出栈中左括号上面的所有元素
                    while (!stack.isEmpty() && stack.peek() != '(') {
                        // 加入到后缀表达式中
                        builder.append(stack.pop());
                    }
                    // 弹出左括号
                    stack.pop();
                }
                // 处理加减乘除
                case '+', '-', '*', '/' -> {
                    while (true) {
                        // 处理栈为空或者栈顶是左括号
                        if (stack.isEmpty() || stack.peek() == '(') {
                            // 压入栈并退出循环
                            stack.push(c);
                            break;
                        }
                        // 处理栈不为空并且栈顶不是左括号
                        else {
                            // 遍历到的运算符的优先级大于栈顶的运算符的优先级
                            if (priority(stack.peek()) < priority(c)) {
                                // 压入栈并退出循环
                                stack.push(c);
                                break;
                            }
                            // 遍历到的运算符的优先级小于或等于栈顶的运算符的优先级
                            else {
                                // 弹出栈顶运算符并加到后缀表达式中
                                builder.append(stack.pop());
                            }
                        }
                    }
                }
                // 处理非运算符或者非括号的字符
                default -> // 直接加到后缀表达式中
                        builder.append(c);
            }
        }
        // 遍历中缀表达式结束后，把栈中所有运算符加到后缀表达式中
        while (!stack.isEmpty()) {
            builder.append(stack.pop());
        }
        // 返回后缀表达式
        return builder.toString();
    }

    /**
     * 中缀表达式转后缀表达式
     * @param exp 中缀表达式
     * @return 后缀表达式
     */
    public static String[] infixToSuffix(String[] exp) {
        String[] result = new String[exp.length]; // 用于构造后缀表达式
        LinkedList<String> stack = new LinkedList<>();
        int index = 0;
        // 遍历中缀表达式
        for (String s : exp) {
            switch (s) {
                // 处理左括号
                case "(" -> // 直接压入栈中
                        stack.push(s);
                // 处理右括号
                case ")" -> {
                    // 弹出栈中左括号上面的所有元素
                    while (!stack.isEmpty() && !stack.peek().equals("(")) {
                        // 加入到后缀表达式中
                        result[index++] = stack.pop();
                    }
                    // 弹出左括号
                    stack.pop();
                }
                // 处理加减乘除
                case "+", "-", "*", "/" -> {
                    while (true) {
                        // 处理栈为空或者栈顶是左括号
                        if (stack.isEmpty() || stack.peek().equals("(")) {
                            // 压入栈并退出循环
                            stack.push(s);
                            break;
                        }
                        // 处理栈不为空并且栈顶不是左括号
                        else {
                            // 遍历到的运算符的优先级大于栈顶的运算符的优先级
                            if (priority(stack.peek()) < priority(s)) {
                                // 压入栈并退出循环
                                stack.push(s);
                                break;
                            }
                            // 遍历到的运算符的优先级小于或等于栈顶的运算符的优先级
                            else {
                                // 弹出栈顶运算符并加到后缀表达式中
                                result[index++] = stack.pop();
                            }
                        }
                    }
                }
                // 处理非运算符或者非括号的字符
                default -> // 直接加到后缀表达式中
                        result[index++] = s;
            }
        }
        // 遍历中缀表达式结束后，把栈中所有运算符加到后缀表达式中
        while (!stack.isEmpty()) {
            result[index++] = stack.pop();
        }
        // 去掉括号后用""补充
        while (index < exp.length){
            result[index++] = "";
        }
        // 返回后缀表达式
        return result;
    }

    /**
     * 计算中缀表达式
     * @param exp 中缀表达式
     * @return 计算结果
     */
    public static int evalInfix(String[] exp){
        String[] suffix = infixToSuffix(exp);
        return evalRPN(suffix);
    }

    /**
     * 计算运算符的优先级
     *
     * @param operator 运算符
     * @return 优先级，加减为1，乘除为2
     */
    private static int priority(char operator) {
        if (operator == '+' || operator == '-') {
            return 1;
        } else if (operator == '*' || operator == '/') {
            return 2;
        } else {
            throw new IllegalArgumentException("参数" + operator + "不是运算符");
        }
    }

    /**
     * 计算运算符的优先级
     *
     * @param operator 运算符
     * @return 优先级，加减为1，乘除为2
     */
    private static int priority(String operator) {
        if (operator.equals("+") || operator.equals("-")) {
            return 1;
        } else if (operator.equals("*") || operator.equals("/")) {
            return 2;
        } else {
            throw new IllegalArgumentException("参数" + operator + "不是运算符");
        }
    }

    /**
     * 反编译得出结论：计算机运算时用的后缀表达式
     */
    public static void test() {
        int a = 10;
        int b = 20;
        int c = 30;
        int d = (a + b) * c;
    }

    public static void main(String[] args) {
        test();
    }
}
